#include <iostream>
#include <cstdlib>
#define MAX_DEPTH 3
#define M 17
using namespace std;

int matrix[17][17];

int count = 0;

struct Shape
{
	int score;
	char shape[10];
};

struct Shape Score_Shape[30] = 
{
	{50,"01100"},
    {50,"00110"},
    {200,"11010"},
    {500,"00111"},
    {500,"11100"},
    {5000,"01110"},
    {5000,"010110"},
    {5000,"011010"},
    {5000,"11101"},
    {5000,"11011"},
    {5000,"10111"},
    {5000,"11110"},
    {5000,"01111"},
    {50000,"011110"},
    {99999999,"11111"},
    {-50,"02200"},
    {-50,"00220"},
    {-200,"22020"},
    {-500,"00222"},
    {-500,"22200"},
    {-5000,"02220"},
    {-5000,"020220"},
    {-5000,"022020"},
    {-5000,"22202"},
    {-5000,"22022"},
    {-5000,"20222"},
    {-5000,"22220"},
    {-5000,"02222"},
    {-50000,"022220"},
    {-99999999,"22222"}
};//计分表

//AIONE AI先手
void Function();
void Computer_Move();
void Intialize_for_Weight();
int Horizontal(int x,int y,int role);
int Longitudinal(int x,int y,int role);
int Left_Oblique(int x,int y,int role);
int Right_Oblique(int x,int y,int role);
int Computer[M][M][4];
int Player[M][M][4];
int Weight_Computer[M][M];
int Weight_Player[M][M];
int Max,Max_x,Max_y;//权重最大的位置，AI落点处

//AITWO AI后手
//int MinMax(int depth);
int Score_evaluation(char *str);//返回值是在该条路上获得的分数，注意，x和y在上一层给出了
int Sum_evaluation();//返回值是当前棋局的评估值
void AI_move();
void legalmove(int *x_min,int *y_max,int *x_max,int *y_min);
int MaxFun(int depth);
int MinFun(int depth);
int alpha;
int beta;

int best_x;
int best_y;//只有在深度为0的时候才可以改变这两个值。

void Intialize_for_Weight()
{
	Max = 0;
	Max_x = 0;
	Max_y = 0;
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<M;j++)
		{
			Weight_Computer[i][j] = 0;
			Weight_Player[i][j] = 0;
			for(int k=0;k<4;k++)
			{
				Computer[i][j][k] = 0;
				Player[i][j][k] = 0;
			}
		}
	}
}

//Function()用于先手
void Function()
{
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(matrix[i][j] != 0 && matrix[i][j] != 9)//该区域有子
			{
				for(int k=0;k<4;k++)
				{
					Computer[i][j][k] = 0;
					Player[i][j][k] = 0;
				}
			}
			else if(matrix[i][j] == 0)
			{
				//这些函数的含义是什么?
				Computer[i][j][0] = Horizontal(i,j,2);//判断水平线
				Computer[i][j][1] = Longitudinal(i,j,2);//判断垂直线
				Computer[i][j][2] = Left_Oblique(i,j,2);//左对角线
				Computer[i][j][3] = Right_Oblique(i,j,2);//右对角线
				Player[i][j][0] = Horizontal(i,j,1);
				Player[i][j][1] = Longitudinal(i,j,1);
				Player[i][j][2] = Left_Oblique(i,j,1);
				Player[i][j][3] = Right_Oblique(i,j,1);
			}
		}
    }
}

//以下相当于判断某白子或者黑子的连线
int Horizontal(int x,int y,int role)
{
    int sum = 0;
    for(int i = x+1;i < M;i++)
    {
        if(matrix[i][y] == role) sum += 1;
        else break;
    }
    for(int i = x-1;i >= 0;i--)
    {
        if(matrix[i][y] == role) sum += 1;
        else break;
    }
    if(sum == 4) sum = 100;
    return sum;
}
int Longitudinal(int x,int y,int role)
{
    int sum = 0;
    for(int i = y+1;i < M;i++)
    {
        if(matrix[x][i] == role) sum += 1;
        else break;
    }
    for(int i = y-1;i >= 0;i--)
    {
        if(matrix[x][i] == role) sum += 1;
        else break;
    }
    if(sum == 4) sum = 100;
    return sum;
}
int Left_Oblique(int x,int y,int role)
{
    int sum = 0;
    for(int i = 1;(i < M - x&&i < M - y);i++)
    {
        if(matrix[x+i][y+i] == role) sum += 1;
        else break;
    }
    for(int i = 1;(i <= x&&i <= y);i++)
    {
        if(matrix[x-i][y-i] == role) sum += 1;
        else break;
    }
    if(sum == 4) sum = 100;
    return sum;
}

int Right_Oblique(int x,int y,int role)
{
    int sum = 0;
    for(int i = 1;(i < M - x&&i <= y);i++)
    {
        if(matrix[x+i][y-i] == role) sum += 1;
        else break;
    }
    for(int i = 1;(i <= x&&i < M - y);i++)
    {
        if(matrix[x-i][y+i] == role) sum += 1;
        else break;
    }
    if(sum == 4) sum = 100;
    return sum;
}

void Computer_Move()
{
    for(int i = 0;i < M;i++)
    {
        for(int j = 0;j < M;j++)
        {
            for(int k = 0;k < 4;k++)
            {
                Weight_Computer[i][j] += Computer[i][j][k];
                Weight_Player[i][j] += Player[i][j][k];
            }
            if(Weight_Computer[i][j] > Max)
            {
                Max_x = i;
                Max_y = j;
                Max = Weight_Computer[i][j];
            }
            if(Weight_Player[i][j] > Max)
            {
                Max_x = i;
                Max_y = j;
                Max = Weight_Player[i][j];
            }
        }
    }
    matrix[Max_x][Max_y] = 2;
}

int My_strstr(char *str, char *sub_str)
{
    char *str_local = NULL;
    char *sub_str_local = NULL;
    int num = 0;
    if(!str || !sub_str)
    {
        cerr<<"Error: str or sub_str is null"<<endl;
        return 0;
    }

    while(*str)
    {
        str_local = str;
        sub_str_local = sub_str;
        do
        {
            if(*sub_str_local == '\0')
            {
                num++;
                break;
            }
        }while(*str_local++ == *sub_str_local++);
        str += 1;
    }
    return num;
}

char *Transform(int type,int x,int y)//注意这个函数 1 是从左向右查找， 2是从上到下查找。3是左上到右下查找，4是从右上到左下查找
{
    int i;
    static char result[M+1];
    if(type == 1)
    {
        for(i = 0;i < M;i++)
        {
            result[i] = matrix[x][i] + '0';
        }
        result[i] = '\0';
        return result;
    }
    if(type == 2)
    {
        for(i = 0;i < M ;i++)
        {
            result[i] = matrix[i][y] + '0';
        }
        result[i] = '\0';
        return result;
    }
    if(type == 3)//右斜线
    {
        for(i = 0;(i+x < M&&i+y < M);i++)
        {
            result[i] = matrix[x+i][y+i] + '0';
        }
        result[i] = '\0';
        return result;
    }
    if(type == 4)//左斜线
    {
        for(i = 0; (x+i < M&&y - i >= 0); i++)
        {
            result[i] = matrix[x+i][y-i] + '0';
        }
        result[i] = '\0';
        return result;
    }
    return NULL;
}

int Score_evaluation(char *str)
{
    int sum  = 0;
    for(int i = 0;i < 30;i++)
    {
        sum += Score_Shape[i].score * My_strstr(str,Score_Shape[i].shape);
    }

    return sum;
}
int Sum_evaluation()
{
    int x,y;
    int sum = 0;
    for(int i = 0;i < M;i++)
    {
        x = i;
        y = 0;
        sum += Score_evaluation(Transform(1,x,y));
    }
    for(int i = 0;i < M;i++)
    {
        x = 0;
        y = i;
        sum += Score_evaluation(Transform(2,x,y));
    }
    for(int i = 0;i < M - 4;i++)
    {
        x = 0;
        y = i;
        sum += Score_evaluation(Transform(3,x,y));
    }
    for(int i = 1;i < M - 4;i++)
    {
        x = i;
        y = 0;
        sum += Score_evaluation(Transform(3,x,y));
    }
    for(int i = 4;i < M;i++)
    {
        x = 0;
        y = i;
        sum += Score_evaluation(Transform(4,x,y));
    }
    return sum;
}
//这个函数相当于判断AI落点的合法位置
void legalmove(int *x_min,int *y_max,int *x_max,int *y_min)
{
    int c;
    *x_min = M - 1;
    *y_max = 0;
    *x_max = 0;
    *y_min = M - 1;
    for(int i = 0;i < M;i++)
    {
        for(int j = 0;j < M;j++)
        {
            if(matrix[i][j] != 0 && matrix[i][j] != 9)
            {
                if(i >= *x_max)
                {
                    *x_max = i;
                }
                if(i <= *x_min)
                {
                    *x_min = i;
                }
                if(j >= *y_max)
                {
                    *y_max = j;
                }
                if(j <= *y_min)
                {
                    *y_min = j;
                }
            }
        }
    }
    if(*x_max + 1 < M) *x_max = *x_max + 1;
    if(*x_min - 1 >= 0) *x_min = *x_min - 1;
    if(*y_max + 1 < M) *y_max = *y_max + 1;
    if(*y_min - 1 >= 0) *y_min = *y_min - 1;
    if(*x_max < *x_min)
    {
        c = *x_max;
        *x_max = *x_min;
        *x_min = c;
    }
    if(*y_max < *y_min)
    {
        c = *y_max;
        *y_max = *y_min;
        *y_min = c;
    }
    return;
}

void AI_move()
{
    if(count == 0)//回合数
    {
        matrix[8][8] = 1;
        best_x = 8;
        best_y = 8;
        return;
    }
    else//除第一步外其他下子策略根据极小化极大算法判断
    {
        MaxFun(1);
    }
    matrix[best_x][best_y] = 1;
}

int MaxFun(int depth)
{
    int i,j;
    int best = -9999999;
    int temp;
    int x_max;
    int x_min;
    int y_max;
    int y_min;
    if(depth == MAX_DEPTH)
    {
        return Sum_evaluation();
    }
    legalmove(&x_min,&y_max,&x_max,&y_min);
    for(i = x_min;i <= x_max;i++)
    {
        for(j = y_min;j <= y_max;j++)
        {
            if(matrix[i][j] == 0)
            {
                matrix[i][j] = 1;
                temp = MinFun(depth+1);
                matrix[i][j] = 0;
                if(temp > best)
                {
                    best = temp;
                    if(depth == 1)
                    {
                        best_x = i;
                        best_y = j;
                    }
                }
            }
        }
    }
    return best;
}
int MinFun(int depth)
{
    int i,j;
    int best = 9999999;
    int temp;
    int x_max;
    int x_min;
    int y_max;
    int y_min;
    if(depth == MAX_DEPTH)
    {
        return Sum_evaluation();
    }
    legalmove(&x_min,&y_max,&x_max,&y_min);
    for(i = x_min;i <= x_max;i++)
    {
        for(j = y_min;j <= y_max;j++)
        {
            if(matrix[i][j] == 0)
            {
                matrix[i][j] = 2;
                temp = MaxFun(depth+1);
                matrix[i][j] = 0;
                if(temp < best)
                {
                    best = temp;
                    /*if(depth == 1)
                    {
                        best_x = i;
                        best_y = j;
                    }*/
                }
            }
        }
    }
    return best;
}

int logic(int i,int j,int matrix[17][17])
{
    int count=1;
    for(int i1=i-1;i1>1 && matrix[i1][j]==matrix[i][j];i1--) count++;
    for(int i2=i+1;i2<15 && matrix[i2][j]==matrix[i][j];i2++) count++;
    if(count>=5)
    return matrix[i][j];

    count = 1;
    for(int j1=j-1;j1>1 && matrix[i][j1]==matrix[i][j];j1--) count++;
    for(int j2=j+1;j2<15 && matrix[i][j2]==matrix[i][j];j2++) count++;
    if(count>=5)
    return matrix[i][j];

    count = 1;
    for(int i3 = i-1,j3 = j-1;i3>1 && j3>1 && matrix[i3][j3]==matrix[i][j];i3--,j3--) count++;
    for(int i4 = i+1,j4 = j+1;i4<15 && j4<15 && matrix[i4][j4]==matrix[i][j];i4++,j4++) count++;
    if(count>=5)
    return matrix[i][j];

    count = 1;
    for(int i5 = i-1,j5 = j+1;i5>1 && j5<15 && matrix[i5][j5]==matrix[i][j];i5--,j5++) count++;
    for(int i6 = i+1,j6 = j-1;i6<15 && j6>1 && matrix[i6][j6]==matrix[i][j];i6++,j6--) count++;
    if(count>=5)
    return matrix[i][j];

    return 0;
}

int main()
{
    Max = 0;
    Max_x = 0;
    Max_y = 0;
    for (int i = 0; i < 17; i++)
    {
        matrix[0][i] = 9;
        matrix[i][0] = 9;
        matrix[16][i] = 9;
        matrix[i][16] = 9;
    }
    for(int i=1;i<16;i++)
    {
        for(int j=1;j<16;j++)
        {
            matrix[i][j]=0;

        }
    }
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<M;j++)
        {
            Weight_Computer[i][j]=0;
            Weight_Player[i][j]=0;
            for(int k=0;k<4;k++)
            {
                Computer[i][j][k]=0;
                Player[i][j][k]=0;
            }
        }
    }

    for(int i=0;i<17;i++)
        {
            for(int j=0;j<17;j++)
            {
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
  

    bool flag=false;
    int num=1;
    cout<<"Black turn"<<endl;
    while(!flag)
    {
        int x,y;
        if(num==1)
        {
            AI_move();
            x = best_x;
            y = best_y;
            num=2;
        }
        else
        {
            cout<<"Please input the position of your chess(x,y):";
            cin>>x>>y;
            if(matrix[x][y]!=0)
            {
                cout<<"This position has been occupied, please choose another one!"<<endl;
                continue;
            }
            matrix[x][y]=num;
            num=1;
        }
        for(int i=1;i<16;i++)
        {
            for(int j=1;j<16;j++)
            {
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
        if(logic(x,y,matrix)>0)
        {
            flag=true;
            if(logic(x,y,matrix)==1)
            {
                cout<<"Black win!"<<endl;
            }
            else
            {
                cout<<"White win!"<<endl;
            }
        }
        else
        {
            if(num==1)
            {
                cout<<"Black turn"<<endl;
            }
            else
            {
                cout<<"White turn"<<endl;
            }
        }
        count++;
    }
    return 0;
}